#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <string>


//微信红包
//https://www.nowcoder.com/questionTerminal/fbcf95ed620f42a88be24eb2cd57ec54
//class Gift {
//public:
//    int getValue(vector<int> gifts, int n) {
//        int mid = n / 2;
//        int max = gifts[0];
//        int min = gifts[0];
//        for (const auto& s : gifts)
//        {
//            if (max < s)
//            {
//                max = s;
//            }
//            if (min > s)
//            {
//                min = s;
//            }
//        }
//        int range = max - min + 1;
//        vector<int> v(range, 0);
//        for (const auto& s : gifts)
//        {
//            ++v[s - min];
//        }
//        for (const auto& s : gifts)
//        {
//            if (v[s - min] >= mid)
//            {
//                return s;
//            }
//        }
//        return 0;
//    }
//};

//计算字符串的编辑距离(动态规划学习)
//https://www.nowcoder.com/questionTerminal/3959837097c7413a961a135d7104c314
// int main() {
//     string s1, s2;
//     while (cin >> s1 >> s2) {
//         int n1 = s1.size();
//         int n2 = s2.size();

//         if (n1 == 0 || n2 == 0)
//             return n1 == 0 ? n2 : n1;

//         //dp[i][k] 表示在s1的前i个字符和s2的前k个字符中最小编辑距离
//         vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));

//         //当s1为空串时 其编辑距离为n1
//         for (int i = 1; i <= n1; ++i)
//             dp[i][0] = i;

//         for (int i = 1; i <= n2; ++i)
//             dp[0][i] = i;

//         for (int i = 1; i <= n1; ++i)
//             for (int k = 1; k <= n2; ++k)
//             {
//                 if (s1[i - 1] == s2[k - 1])
//                 {
//                     //如果字符相同 则等于删除增加+1(删除增加都算编辑)
//                     dp[i][k] = 1 + min(dp[i - 1][k], dp[i][k - 1]);
//                     //以及替换中最小编辑距离
//                     dp[i][k] = min(dp[i][k], dp[i - 1][k - 1]);
//                 }
//                 else
//                 {
//                     //如果字符相同 则等于删除增加+1
//                     dp[i][k] = 1 + min(dp[i - 1][k], dp[i][k - 1]);
//                     //以及替换中最小编辑距离+1(替换后字符串)
//                     dp[i][k] = min(dp[i][k], 1 + dp[i - 1][k - 1]);
//                 }
//             }

//         cout << dp[n1][n2] << endl;
//     }
//     return 0;
// }